#ifndef PRIORITY_QUEUE_H
#define PRIORITY_QUEUE_H

#include<iostream>
#include<vector>
using std::cout;
using std::vector;

//仿函数——less是小于，greater是大于
template<class T>
struct less{
	bool operator()(const T& x1, const T& x2){
		return x1 < x2;
	}
};

template<class T>
struct greater{
	bool operator()(const T& x1, const T& x2){
		return x1 > x2;
	}
};

//引入仿函数进行控制大堆还是小堆,默认是大堆
template<class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue{
public:
	//向上调整法
	void AdjustUp(int child){
		Compare com;//仿函数对象
		//找到父节点的下标
		int parent = (child - 1) / 2;
		while (child > 0)
		{
			//if (_con[child] > _con[parent])
			if ( com(_con[parent], _con[child]) )
			{
				std::swap(_con[parent], _con[child]);
				child = parent;
				parent = (child - 1) / 2;
			}
			else
			{
				break;
			}			
		}		
	}

	//优先队列底层是一个大堆,通过向上调整法保证堆的性质
	void push(const T x){
		_con.push_back(x);
		//O(logN) 每插入一次就向上调整
		AdjustUp(_con.size() - 1);
	}

	void AdjustDown(int root){
		Compare com;
		//父子节点的下标
		int parent =  root;
		int child = parent * 2 + 1;

		while (child < _con.size())
		{
			//选出左右孩子中大的那一个,前提是有右孩子
			//if(child + 1 < _con.size() && _con[child + 1] > _con[child])
			if(child + 1 < _con.size() && com(_con[child], _con[child + 1]))
			{
				++child;
			}

			//if( _con[child] > _con[parent])
			if ( com(_con[parent], _con[child]) )
			{
				std::swap( _con[child], _con[parent]);
				parent = child;
				child = parent * 2 + 1;
			}
			else{
				break;
			}
		}
		
	}

	void pop(){
		//将首尾的数据交换，然后pop_back最后一个数据，之后向下调整法保持大堆的性质
		std::swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		//O(logN)
		AdjustDown(0);
	}

	T& top(){
		return _con[0];
	}

	size_t size(){
		return _con.size();
	}
	bool empty(){
		return _con.empty();
	}
private:
	Container _con;
};

#endif